<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>快速排序</title>
</head>
<body>

</body>
</html>

<script>
  /*
  * 简单分三个步骤：
  * 1.找基准，以中间项为基准，
  * 2.遍历数组，比基准小的放左，比基准大的放右，
  * 3.递归。
  * */
  const arr = [ 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 ]
  function quickSort(arr){
    //如果数组<=1则返回
    if(arr.length<=1){
      return arr
    }
    //找基准
    var num=Math.floor(arr.length/2)
    //把基准删除
    var numVal=arr.splice(num,1)
    //定义左右数组
    var left=[]
    var right=[]
    //比基准小的放在左，比基准大的放在右
    for(i=0;i<arr.length;i++){
      if(arr[i]<numVal){
        left.push(arr[i])
      }else{
        right.push(arr[i])
      }
    }
    //递归
    return [ ...quickSort(left), ...numVal, ...quickSort(right) ]
    // return quickSort(left).concat(numVal,quickSort(right));
  }
  console.log(quickSort(arr))
</script>